package com.atguigui.leetcode1;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 1090.受标签影响的最大值
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/5/23 8:56
 */
public class P1090LargestValuesFromLabels {
    public static void main(String[] args) {
        Solution solution = new P1090LargestValuesFromLabels().new Solution();
        // TO TEST
    }

    class Solution {
        public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
            int n = values.length;
            Integer[] id = new Integer[n];
            for (int i = 0; i < n; i++) {
                id[i] = i;
            }
            //对values中数据的下标进行排序
            Arrays.sort(id, (a, b) -> values[b] - values[a]);

            int ans = 0, choose = 0;
            Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
            //从最大的下标开始拿数
            for (int i = 0; i < n && choose < numWanted; ++i) {
                int label = labels[id[i]];
                //跳过下标数和useLimit相同的
                if (cnt.getOrDefault(label, 0) == useLimit) {
                    continue;
                }
                ++choose;

                ans += values[id[i]];
                cnt.put(label, cnt.getOrDefault(label, 0) + 1);
            }

            return ans;
        }
    }
}
